//
//  CLSort.m
//  Charles
//
//  Created by Leo on 2019/6/4.
//  Copyright © 2019 charles. All rights reserved.
//

#import "CLSortFind.h"

@implementation CLSortFind

/**
 冒泡排序算法 从小到大排列
 
 @param numbers 将要排序的数组
 @param length 数组长度
 */
void bubbleSort(int numbers[],int length) {
    /* 算法思想： 冒泡排序（英语：Bubble Sort）是一种简单的排序算法。
冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
        算法时间复杂度：最好是O(n) 最坏是O(n2) 平均复杂度O(n2);
     */
    
    if (length <= 1) {
        return;
    }
    for (int i = 0; i < length; i++) {
        // 提前退出冒泡循环的标志位,这是对冒泡排序的一个优化，有不用排序的情况就提前退出循环。如231456，后面的456就不用再排序了。
        bool flag = false;
        for (int j = 0; j < length - i - 1; j++) {
            if ( numbers[j] > numbers[j+1]) {
                int temp = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = temp;
                // 表示有数据交换
                flag = true;
            }
        }
        // 没有数据交换，提前退出
        if (!flag) {
            break;
        }
        NSLog(@"%d %d %d %d %d %d %d %d %d %d",
              numbers[0],numbers[1],numbers[2],
              numbers[3],numbers[4],numbers[5],
              numbers[6],numbers[7],numbers[8],
              numbers[9]);
    }
}

void insertionSort(int numbers[],int length) {
    /*
     基本思想：
     我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束
     */
    if (length <= 1) {
        return;
    }
    for (int i = 1; i < length; i++) {
        int value = numbers[i];
        int j = i - 1;
        // 查找插入的位置
        for (; j >=0; j--) {
            if (numbers[j] > value) {
                numbers[j+1] = numbers[j];
            }else{
                break;
            }
        }
        // 插入数据
        numbers[j + 1] = value;
    }
}


/**
 选择排序
 
 @param numbers 将要排序的数组
 @param length 数组长度
 */
void selectionSort(int numbers[],int length) {
    /* 算法思想：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。
     首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，
     再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
     以此类推，直到所有元素均排序完毕。
     */
    
    for (int i = 0; i < length - 1; i++) {
        // 无序数组的起始位置
        int minIndex = i;
        for (int j = i + 1; j < length; j++) {
            // 查找无序数组中最小的元素
            if (numbers[j] < numbers[minIndex]) {
                minIndex = j;
            }
        }
        // 如果无序数组中的最小元素不是无序数组的起始位置，则交换最小元素
        if (minIndex != i) {
            int tempNumber = numbers[minIndex];
            numbers[minIndex] = numbers[i];
            numbers[i] = tempNumber;
        }
        NSLog(@"%d %d %d %d %d %d %d %d %d %d",
              numbers[0],numbers[1],numbers[2],
              numbers[3],numbers[4],numbers[5],
              numbers[6],numbers[7],numbers[8],
              numbers[9]);
    }
}

/**
 快速排序算
 
 @param numbers 将要排序的数组
 @param left 左边
 @param right 右边
 */
void quickSort(int numbers[],int left,int right) {
    /*
     算法思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
     然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据编程有序序列。
     */
    if (left >= right) {
        return;
    }
    int i = left;
    int j = right;
    int key = numbers[left];
    /*
     一趟循环都做了什么：
     找出一个比key小的放在key左边，找出一个比key大的放在key右边
     */
    // 方法一
    while (i < j) {
        // 此时，key在下标为i的位置。然后从j向i遍历 即：从后向前遍历，找到比key 小的元素 将它和key 所在的元素交换
        while (i < j) {
            if (numbers[j] <= key) {
                int temp = numbers[j];
                numbers[j] = numbers[i];
                numbers[i] = temp;
                break;
            }
            j--;
        }
        
        // 此时，key在下标为j的位置。 然后从i向j 即：从前向后前遍历，找到比key 大的元素 将它和key 所在的元素交换
        while (i < j) {
            if (numbers[i] >= key) {
                int temp = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = temp;
                break;
            }
            i++;
        }
    }
    // 此时key在下标为i的位置
    // 对key左边的元素进行快速排序
    quickSort(numbers, left, i-1);
    // 对key右边的元素进行快速排序
    quickSort(numbers, i+1, right);
    
    /* 方法二
     while (i < j) {
     while (i < j && numbers[j] >= key) {
     j--;
     }
     numbers[i] = numbers[j];
     while (i < j && numbers[i] <= key) {
     i++;
     }
     numbers [j] = numbers[i];
     }
     numbers[i] = key;
     NSLog(@"%d %d %d %d %d %d %d %d %d %d",
     numbers[0],numbers[1],numbers[2],
     numbers[3],numbers[4],numbers[5],
     numbers[6],numbers[7],numbers[8],
     numbers[9]);
     
     quickSort(numbers,left,i-1);
     quickSort(numbers,i+1,right);
     */
}

/**
 二分查找算法
 
 @param numbers 被查找的有序数组
 @param startIndex 起始位置
 @param numberLength 将要查找的长度
 */
void binarySearch(int numbers[],int startIndex,int numberLength) {
    if (startIndex > numberLength) {
        NSLog(@"sorry have no this number!");
        return;
    }
    int keyNumber = 0;
    int middleIndex = startIndex + (numberLength - startIndex)/2;
    NSLog(@"middleIndex is %d",middleIndex);
    // 如果正好是numbers[middleIndex] 则结束查找
    if (keyNumber == numbers[middleIndex]) {
        NSLog(@"find out key number at index:%d value:%d",middleIndex,numbers[middleIndex]);
        return;
    }
    // 如果目标元素在中间元素的左边
    if (keyNumber < numbers[middleIndex]) {
        binarySearch(numbers,startIndex,middleIndex - 1);
    }
    // 如果目标元素在中间元素的右边
    else {
        binarySearch(numbers,middleIndex + 1,numberLength);
    }
}

int binarySearchWithWhile (int numbers[],int length,int searchKey){
    int low = 0;
    int high = length - 1;
    while (low <= high) {
        int middle = (low + high)/2;
        // 正好命中
        if (numbers[middle] == searchKey) {
            return middle;
        }
        // 左边查找
        else if (numbers[middle] > searchKey){
            high = middle - 1;
        }
        // 右边查找
        else if (numbers[middle] < searchKey){
            low = middle + 1;
        }
    }
    return -1;
}


@end
